package linked;

/**
 * @author
 * @date 2025/5/14 16:38
 */
public class 删除倒数第N个节点 {
    public static void main(String[] args) {
        LinkedNode header = new LinkedNode("01");
        LinkedList linkedList = new LinkedList(header);
        linkedList.add(new LinkedNode("02"));
        linkedList.add(new LinkedNode("03"));
        linkedList.add(new LinkedNode("04"));
        linkedList.add(new LinkedNode("05"));
        linkedList.print();
        delete02(5,linkedList);
        System.out.println();
        linkedList.print();
    }

    /**
     * 删除第倒数第n个节点，就是删除正数（size+1-n）个节点
     */
    public static void delete(int i,LinkedList linkedList){
        LinkedNode cur = linkedList.header;
        int size = 0;
        while (cur!=null){
            cur = cur.next;
            size++;
        }
        if(i==size){
            // 单独处理删除第一个节点
            linkedList.header = linkedList.header.next;
            return;
        }
        int j = 1;
        LinkedNode target = linkedList.header;
        while (size-i!=j&&target.next!=null){
            target = target.next;
            j++;
        }
        // 删除target
        target.next = target.next.next;

    }

    /**
     * 快慢指针：快指针相比慢指针提前多少步到达末尾，对于慢指针而言，就是倒数第n个
     * 快指针先走n-1步，然后快慢指针一直以步长为1的间隔走到末尾即可
     */

    public static void delete02(int i ,LinkedList linkedList) {
        LinkedNode slow = linkedList.header;
        LinkedNode fast = linkedList.header;
        LinkedNode pre = slow;
        int j = i;
            // 快指针先走走n步
        while (j > 1 && fast.next != null) {
            fast = fast.next;
            j--;
        }


        // 快慢指针同时移动
        while (fast.next!=null){
            pre = slow;
            fast = fast.next;
            slow= slow.next;
        }

        if(pre == linkedList.header){
            // 删除头节点
            linkedList.header = pre.next;
            return;
        }
        // 删除节点
        pre.next = slow.next;

    }
}
